//1.分治-快速排序-颜色分类
//数组分三块思想:
//[0, l] [l + 1, i - 1] [i, r - 1] [r, n - 1]
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = -1, r = nums.size(), i = 0;
        while(i < r)
        {
            if(nums[i] == 0) swap(nums[i++], nums[++l]);
            else if(nums[i] == 1) i++;
            else swap(nums[i], nums[--r]);
        }
    }
};

//2.分治-快速排序-排序数组
class Solution {
public:
    int get_random(vector<int>& nums, int l, int r)
    {
        return nums[l + rand() % (r - l + 1)];
    }

    void quick_sort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;
        //1.随机选择基准元素
        int p = get_random(nums, left, right); 
        //2.数组分三块
        //[left, l] [l + 1, i - 1] [i, r - 1] [r, right]
        int i = left, l = left - 1, r = right + 1;
        while(i < r)
        {
            if(nums[i] == p) i++;
            else if(nums[i] < p) swap(nums[i++], nums[++l]);
            else swap(nums[i], nums[--r]);
        }
        //3.递归左右区间
        quick_sort(nums, left, l);
        quick_sort(nums, r, right);
    }

    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned int)time(nullptr));
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};